/*************************************************************************
	> File Name: queue.c
	> Author: Wang Bo
	> Mail: 1276106221@qq.com
	> Created Time: 2020年12月03日 星期四 15时17分09秒
 ************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

Queue *initQueue(int size) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * size);
    q->size = size;
    q->cnt = 0;
    q->tail = 0;
    q->head = 0;
    return q;
}

void clearQueue(Queue *q) {
    if (q == NULL) return ;
    free(q->data);
    free(q);
    return;
}

int pushQueue(Queue *q, int val) {
    if (q == NULL) return 0;
    if (q->cnt == q->size) {
        if(!expandQueue(q)) return 0;
        printf("扩容成功，当前容量%d -- ", q->size);
    }
    q->data[q->tail++] = val;
    if (q->tail == q->size) {
        q->tail = 0;
    }
    q->cnt++;
    return 1;
}

int popQueue(Queue *q) {
    if (q == NULL) return 0;
    if (isEmptyQueue(q)) return 0;
    q->head++;
    if (q->head == q->size) q->head = 0;
    q->cnt--;
    return 1;
}

int isEmptyQueue(Queue *q) {
    if (q == NULL) return 1;
    return q->cnt == 0;
}

int expandQueue(Queue *q) {
    int *newdata;
    int extSize = q->size;
    while (extSize) {
        newdata = (int *)calloc((q->size + extSize), sizeof(int));
        if (newdata == NULL) extSize >>= 1;
        else break;
    }
    if (newdata == NULL) return 0;
    for (int i = q->head, j = 0; j < q->cnt; ++j) {
        newdata[j] = q->data[(i + j) % q->size];
    }
    free(q->data);
    q->data = newdata;
    q->size += extSize;
    q->head = 0;
    q->tail = q->cnt;
    return 1;
}

int frontQueue(Queue *q) {
    if (q == NULL || isEmptyQueue(q)) return -1;
    return q->data[q->head];
}

void outputQueue(Queue *q) {
    if (q == NULL || isEmptyQueue(q)) return ;
    printf("Queue :[");
    for (int i = q->head, j = 0; j < q->cnt; ++j) {
        j && printf(", ");
        printf("%d", q->data[(i + j) % q->size]);
    }
    printf("]\n");
    return ;
}
